package exercises.leetcode;

/**
 * <a href="https://leetcode-cn.com/problems/house-robber-ii/">
 * 213. 打家劫舍 II</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
 * <p>
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
 *
 * @author or2
 * @date 2021年09月21日 时间: 21:13
 */
public class No213 {
    public int rob(int[] nums) {
        if (nums.length < 4) {
            int max = nums[0];
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] > max) {
                    max = nums[i];
                }
            }
            return max;
        }

        /*包含第一件房子*/
        int p = nums[0];
        int q = Math.max(p, nums[1]);
        for (int i = 2, ans; i < nums.length - 1; i++) {
            ans = Math.max(p + nums[i], q);
            p = q;
            q = ans;
        }
        int max1 = q;

        /*包含最后一件房子*/
        p = nums[1];
        q = Math.max(p, nums[2]);
        for (int i = 3, ans; i < nums.length; i++) {
            ans = Math.max(p + nums[i], q);
            p = q;
            q = ans;
        }
        return Math.max(q, max1);
    }
}
